﻿// https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247489967&idx=2&sn=a2ecb515d22c78f65e67586760e75f8e&scene=21#wechat_redirect
// https://leetcode-cn.com/problems/reverse-words-in-a-string/

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>

using namespace std;

// struct ListNode {
//     int val;
//     ListNode *next;
//     ListNode() : val(0), next(nullptr) {}
//     ListNode(int x) : val(x), next(nullptr) {}
//     ListNode(int x, ListNode *next) : val(x), next(next) {}
// };

class Solution {
public:
    string reverseWords(string s) {
        EliminateSpace(s);
        ReverseString(s, 0, s.size() - 1);
        int start = 0;
        int end = 0;
        bool entry = false;

        for (int i = 0; i < s.size(); i++) {
            if (!entry) {
                start = i;
                entry = true;
            }
            if (entry && s[i] == ' ' && s[i - 1] != ' ') {
                end = i - 1;
                entry = false;
                ReverseString(s, start, end);
            }
            if (entry && i == s.size() - 1 && s[i] != ' ') {
                end = i - 1;
                entry = false;
                ReverseString(s, start, end);
            }
        }
        return s;
    }
    
    void EliminateSpace(string& s) {
        int fast = 0, slow = 0;

        while (s.size() > 0 && s[fast] == ' ' && fast < s.size()) {
            fast++;
        }
        for (; fast < s.size(); fast++) {
            if (s[fast] == ' ' && s[fast] == s[fast - 1] && fast - 1 > 0) {
                continue;
            } else {
                s[slow++] = s[fast];
            }
        }
        if (slow - 1 > 0 && s[slow - 1] == ' ') {
            s.resize(slow - 1);
        } else {
            s.resize(slow);
        }
    }

    void ReverseString(string& s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }
};

int main() {
    Solution obj = Solution();
    cout << obj.reverseWords("  hel ld!  ");
}